import sys
class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        # r = len(grid)
        # l = len(grid[0])
        # if l==0 or r==0:
        #     return 0
        # f = [[0] * l for _ in range(r)]
        # for i in range(r):
        #     for j in range(l):
        #         if i==0 and j==0:
        #             f[i][j]=grid[i][j]
        #         else:
        #             f[i][j]=grid[i][j]
        #             if i-1>=0:
        #                 t1 = f[i - 1][j]
        #             else:
        #                 t1 = sys.maxsize
        #
        #             if j-1>=0:
        #                 t2 = f[i][j-1]
        #             else:
        #                 t2 = sys.maxsize
        #
        #             f[i][j] = min(t1,t2) + grid[i][j]
        # return f[-1][-1]



        #
        # r = len(grid)
        # l = len(grid[0])
        # if l==0 or r==0:
        #     return 0
        # f = [[0] * l for _ in range(2)]
        # now = 0
        # for i in range(r):
        #     old = now
        #     now = 1 - now
        #     for j in range(l):
        #         if i==0 and j==0:
        #             f[now][j] = grid[i][j]
        #         else:
        #             f[now][j] = grid[i][j]
        #             if i - 1 >= 0:
        #                 t1 = f[old][j]
        #             else:
        #                 t1 = sys.maxsize
        #             if j - 1 >= 0:
        #                 t2 = f[now][j-1]
        #             else:
        #                 t2 = sys.maxsize
        #             f[now][j] = min(t1, t2) + f[now][j]
        # print(f)
        # return f[now][-1]

        n = len(grid)
        m = len(grid[0])
        if n == 0 or m == 0:
            return 0
        f = [[0] * m for _ in range(n)]
        for i in range(n):
            for j in range(m):
                if i == 0 and j == 0:
                    f[i][j] = grid[i][j]
                else:
                    if i-1>=0:
                        t = f[i-1][j]
                    else:
                        t= sys.maxsize
                    if j-1>=0:
                        t1= f[i][j-1]
                    else:
                        t1 = sys.maxsize
                    f[i][j] = min(t + grid[i][j], t1 + grid[i][j])
        return f[-1][-1]


c = [[1,3,1],[1,5,1],[4,2,1]]
s= Solution()
m = s.minPathSum(c)
print(m)